home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung / Power-Programmierung (Tewi)(1994).iso / magazine / drdobbs / ddjcompr / hstest / src / pack.c < prev    next >
C/C++ Source or Header  |  1991-04-28  |  9KB  |  376 lines
  1. //************************************************************************
  2. // PACK.C
  3. // Modul zur Datenkomprimierung
  4. // Idee und Implementierung tom ehlert '90
  5. //
  6. // Datenaufzeichnungsformat 
  7. //
  8. //    die Idee die dahintersteckt funktioniert wie folgt :
  9. //  wenn der derzeitige String bereits gesendet worden ist, kodiere
  10. //  ihn als kombination von index,laenge in die bereits empfangenen Daten
  11. //  als 2-Bytekombination.
  12. //
  13. //    Das genaue Format ist wohl am besten durch UNPACK beschrieben, man 
  14. //    macht dann auch keine Fehler in der Dokumentation.
  15. //
  16. //  Das Schema laeuft wie folgt :
  17. //    
  18. //    Das jeweils erste Byte decodiert 8 Gruppen. Bit 7 (0x80) decodiert
  19. //      die erste Gruppe,Bit 6 (0x40) die zweite usf. . Dabei gilt :
  20. //        Bit == 0 --> Gruppe besteht aus 1 Byte, dieses ist in den 
  21. //                Zielpuffer zu kopieren.
  22. //        Bit == 1 --> Gruppe besteht aus komprimierter Information,
  23. //            lese zwei Byte.
  24. //    
  25. //            index  = *pbuffer & SENDLEN  (0x3ff);
  26. //            length = (*pbuffer >> 12) + MIN_LENGTH;            
  27. //            if (length == 0x0f+MIN_LENGTH)
  28. //                length  = pbuffer[2];            /* code is 3 bytes          */
  29. //    
  30. //            memcpy(outbuffer,outbuffer-index,length);
  31. //    
  32. //
  33. // 
  34. //************************************************************************
  35.  
  36. #include <stdio.h>
  37. #include <setjmp.h>
  38. #include "pack.h"
  39. #include "huffman.h"
  40.  
  41.  
  42. typedef unsigned char uchar;
  43.  
  44. #ifdef MSDOS
  45.     #define ONLY_ON_80x86        /* this is ok    */
  46. #else
  47.     #define ONLY_ON_80x86 this runs only on 80x86    // BYTE - ORDER !!
  48. #endif
  49.     
  50.  
  51. #define MIN_LENGTH        3        /* minimum to be compressed */
  52. #define MAXCODELENGTH 0x0f
  53. #define    IBSIZE         0xff
  54. #define SENDLEN        0xfff        /* MUST BE 00001111111 */
  55.  
  56. # define CRBLEN  0x800
  57.  
  58. # define BUFFTAIL (SENDLEN+1)
  59. # define BUFFOVER 0x100
  60.  
  61. #ifdef PACK
  62.  
  63. static uchar sendbuff[  CRBLEN+BUFFTAIL+BUFFOVER] =         {0};
  64. static int   offset1 [1+CRBLEN+BUFFTAIL+BUFFOVER] = {0xffff,0};
  65. #define offset (offset1+1)
  66.  
  67.  
  68. #define NVH 0xffff
  69.  
  70.  
  71.  
  72. //
  73. // Die gewaehlte HASH-Function ist beliebig; sie returned einen
  74. // Wert 0..HASH_SIZE. die vorgeschlagene bietet einen Kompromiss
  75. // zwischen sizeof(last(HASH_SIZE)) und Geschwindigkeit, diese
  76. // wird dadurch aber nicht wesentlich verringert
  77. // 
  78. #define HASH_SIZE (0x400+0x200+0x100)     // (0xff<<2) + (0xff<<1) + 0xff) ?? 
  79. #define HASH_VAL(ptr)    ((ptr)[0] + ((ptr)[1]<<1) + ((ptr)[2] << 2))
  80.  
  81. static int    last[HASH_SIZE] = {0};
  82.  
  83. #define add_list( c, cptr) offset[cptr] = last[c],last[c] = (cptr)
  84.  
  85. /**********************************************************************
  86. ** output buffer waehrend des packens
  87. */
  88. static uchar far *packptr = NULL;
  89. static uchar far *packend = NULL;
  90.  
  91. static uchar far *ibuffer = NULL;
  92. static unsigned short ilen = 0;
  93. static jmp_buf not_packable = {0};
  94.  
  95. static uchar packmask    = 0;
  96. static uchar packmaskbit = 0;
  97. static uchar far *packmaskptr = NULL;
  98.  
  99. static int  tosend = 0;
  100. static int     gesendet = 0;
  101.  
  102. #define STATIC
  103.  
  104. STATIC void  new_mask(void);
  105. STATIC void  send1(void);
  106. STATIC void  send(int  len);
  107. STATIC void  move_buffers(void);
  108. STATIC int   xlen(void);
  109. STATIC void  crunch(void);
  110. STATIC int   rdf(unsigned char  *d,unsigned len);
  111. extern int   _fastcall memid(uchar *s1,uchar *s2);
  112.  
  113. STATIC void new_mask(void)
  114. {
  115.     *packmaskptr = packmask;
  116.     packmaskptr  = packptr++;
  117.     packmaskbit = 0x80;
  118.     packmask    = 0x00;
  119.     if (packptr >= packend)
  120.         longjmp(not_packable,1);
  121. }
  122.  
  123. STATIC void move_buffers(void)
  124. {
  125.     register int *ip, loop,rd;
  126.  
  127.     memcpy(sendbuff,sendbuff+CRBLEN,BUFFTAIL+BUFFOVER);
  128.     memcpy((uchar*)offset  ,(uchar*)(offset  +CRBLEN),
  129.                             sizeof(offset[0])*(BUFFTAIL+BUFFOVER));
  130.     gesendet -= CRBLEN;
  131.     tosend   -= CRBLEN;
  132.     while ((rd = rdf(sendbuff+tosend,sizeof(sendbuff)-tosend)) > 0)
  133.         tosend += rd;
  134.  
  135.     for (ip = last,loop = LENGTH(last);loop ;ip++,--loop)
  136.         if (*ip >= 0)
  137.             *ip -= CRBLEN;
  138.     for (ip = offset,loop = BUFFTAIL+BUFFOVER;loop ;ip++,--loop)
  139.         if (*ip >= 0)
  140.             *ip -= CRBLEN;
  141. }
  142.  
  143.  
  144. STATIC void crunch(void)
  145. {
  146.     register int len,tbs,find_index;
  147.  
  148.     while ((tbs = tosend - gesendet) > 0)
  149.         {
  150.  
  151. //**********************************************************************
  152. // this part is essentially a subroutine, calculating len & find_index
  153. //**********************************************************************
  154. {
  155.     register int sp;
  156.     register int stop_ptr;
  157.     register uchar *sbcheck;
  158.     register short ccheck;
  159.     register uchar *tbs = sendbuff + gesendet;
  160.     register int loop;
  161.     
  162.     len = MIN_LENGTH-1;
  163.     
  164.     stop_ptr = gesendet - SENDLEN;
  165.     if (stop_ptr < 0)
  166.         stop_ptr = 0;
  167.  
  168.     ccheck = *(int*)(tbs+1);
  169.     sbcheck = sendbuff+1;
  170.  
  171.     for (sp = last[HASH_VAL(tbs)];sp >= stop_ptr;sp = offset[sp])
  172.         {
  173.         if (*(short *)(sbcheck+sp) == ccheck) 
  174.             if ((loop = memid(sendbuff+sp,tbs)) > len)
  175.                 {
  176.                 len = loop;
  177.                 ccheck = *(short *)(tbs+len-1);
  178.                 sbcheck = sendbuff+len-1;
  179.  
  180.                 find_index = gesendet - sp;
  181.                 if (len >= IBSIZE)
  182.                     break;
  183.                 }
  184.         }
  185. }
  186.  
  187.         len = min(len,255);
  188.         len = min(len,tbs);
  189.  
  190.  
  191.  
  192.         if (len >= MIN_LENGTH)
  193.  
  194. //**********************************************************************
  195. // another inlined subroutine :
  196. // write len + index
  197. //**********************************************************************
  198.  
  199. {
  200.     register int index;register uchar *ibp;
  201.  
  202.     ONLY_ON_80x86;
  203.         
  204.     if (len < MAXCODELENGTH+MIN_LENGTH)
  205.         {                                // remember : findindex <= SENDLEN !!
  206.         *((int far *)packptr)++ = find_index | ((len -MIN_LENGTH) << 12) ;
  207.         }
  208.     else
  209.         {
  210.         *((int far *)packptr)++ = find_index | (MAXCODELENGTH << 12) ;
  211.         *packptr++ = (uchar)len;
  212.         }
  213.  
  214.     packmask |= packmaskbit;
  215.     if ((packmaskbit >>= 1) == 0)
  216.         new_mask();
  217.  
  218.     ibp = sendbuff+gesendet-1,index=gesendet-1;
  219.     gesendet += len;
  220.     for ( ; len ;    ibp++,index++, --len)
  221.         {
  222.         register int hval = HASH_VAL(ibp);
  223.         add_list(hval,index);
  224.         }
  225.  
  226. }
  227.         else 
  228. //**********************************************************************
  229. // another inlined subroutine :
  230. // write literal character
  231. //**********************************************************************
  232.  
  233. {
  234.     register uchar *s = sendbuff+gesendet;    /* zu sendenden */
  235.     register int hval;
  236.  
  237.     *packptr++ = *s++;
  238.     if ((packmaskbit >>= 1) == 0)
  239.         new_mask();
  240.     
  241.     hval = HASH_VAL(s-2);
  242.     add_list(hval,gesendet-1);
  243.     gesendet++;
  244.  
  245.     if (gesendet > CRBLEN +BUFFTAIL )
  246.         move_buffers();
  247. }
  248.  
  249.     if (gesendet > CRBLEN +BUFFTAIL )
  250.         move_buffers();
  251.  
  252.         }
  253. }
  254.  
  255.  
  256. STATIC int rdf(uchar *d,unsigned len)
  257. {
  258.     len = min(len,ilen);
  259.     memcpy(d,ibuffer,len);
  260.     ilen -= len;
  261.     ibuffer += len;
  262.     return len;
  263. }
  264.  
  265.  
  266. int far _loadds pack(pbuffer,pbufferlen,inbuffer,blen)
  267. uchar far *pbuffer;short pbufferlen;
  268. uchar far *inbuffer;short blen;
  269. {
  270.     int huff_length;
  271.     
  272.     if (blen == 0 || setjmp(not_packable))
  273.         return 0xffff;
  274.  
  275.     ilen = blen;
  276.     ibuffer = inbuffer;
  277.                         /* wenn man die naechsten zwei zeilen vertauscht     */
  278.                         /* und -e eingeschaltet ist verhakelt sich MSC 6.00 */
  279.     packend = pbuffer + pbufferlen - 25;
  280.     packptr = pbuffer;
  281.  
  282.     if (packptr >= packend)
  283.         longjmp(not_packable,1);
  284.  
  285.     packmaskptr  = packptr++;
  286.     packmaskbit = 0x80;
  287.     packmask    = 0x00;
  288.  
  289.     tosend = rdf(sendbuff,CRBLEN+BUFFTAIL+BUFFOVER);
  290.     gesendet = 0;
  291.  
  292.     memset(last   ,NVH,sizeof(last));
  293.     memset(offset1,NVH,min(sizeof(offset1) , blen));
  294.     gesendet = 0;
  295.  
  296.     crunch();
  297.  
  298.     *packmaskptr = packmask;
  299.     if (packmaskbit == 0x80)        // letztes newmask() zuviel
  300.         packptr--;
  301.  
  302.     return packptr - pbuffer;
  303. }
  304. #endif
  305.  
  306. #ifdef UNPACKC
  307.  
  308. //********************************************************************* 
  309. // this is the uncrunching part
  310. // unpackc() is written in C
  311. // unpack()  see UNPACK.ASM
  312. // both routines work identical
  313. //*********************************************************************
  314.  
  315. int far _loadds unpackc(outbuffer,pbuffer,packlen)
  316. uchar far *outbuffer;
  317. uchar far *pbuffer;register int packlen;
  318. {
  319.     register int uloop;
  320.     register uchar packmask;
  321.     int length;unsigned index;
  322.     uchar far *sbuffer = outbuffer;
  323.  
  324.     for (uloop = 1;packlen > 0;packmask <<= 1)
  325.         {
  326.         if (--uloop == 0)
  327.             {
  328.             packmask    = *pbuffer++,packlen--;
  329.             uloop = 8;
  330.             }
  331.         if ((packmask & 0x80) == 0)                /* this byte is literally */
  332.             *outbuffer++ = *pbuffer++,packlen--;
  333.         else
  334.             {                                    /* next 2 bytes coded     */
  335.             ONLY_ON_80x86;
  336.             index = *(int far *)pbuffer;        /* 4 bit length              */
  337.             length = (index >> 12) + MIN_LENGTH;/* 12 bit offset          */
  338.             index &= SENDLEN;
  339.             if (length == MAXCODELENGTH+MIN_LENGTH)    /* length > 18              */
  340.                 {                                /* use next byte for length*/
  341.                 length  = pbuffer[2];            /* code is 3 bytes          */
  342.                 pbuffer += 3;
  343.                 packlen -= 3;
  344.                 }
  345.             else {
  346.                 packlen -= 2;
  347.                 pbuffer += 2;
  348.                 }
  349.                                     /* copy BYTEWISE with OVERWRITE */
  350.             if (index == 1)            // memcpy will not work as it copies WORDS
  351.                 memset(outbuffer,*(outbuffer-1),length);
  352.             else
  353.                 memcpy(outbuffer,outbuffer-index,length);
  354.  
  355.             outbuffer += length;
  356.             }            
  357.         }
  358.     return outbuffer-sbuffer;
  359. }
  360.  
  361. #endif
  362.  
  363. //***********************************************************************
  364. // externe Assmblerroutinen :
  365. //
  366. // memidc(uchar *dest,uchar *src)
  367. //                            //   return number of equal bytes
  368. //    {
  369. //         register uchar *dr = dest;
  370. //    
  371. //         for (; *src++ == *dr ;dr++)
  372. //             ;
  373. //         return dr-dest;
  374. //     }
  375. //***********************************************************************
  376.